home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 1.iso / dist / fw_apache2.idb / usr / freeware / apache2 / include / apr_ring.h.z / apr_ring.h
C/C++ Source or Header  |  2002-07-08  |  18KB  |  494 lines
  1. /* ====================================================================
  2.  * The Apache Software License, Version 1.1
  3.  *
  4.  * Copyright (c) 2000-2002 The Apache Software Foundation.  All rights
  5.  * reserved.
  6.  *
  7.  * Redistribution and use in source and binary forms, with or without
  8.  * modification, are permitted provided that the following conditions
  9.  * are met:
  10.  *
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  *
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in
  16.  *    the documentation and/or other materials provided with the
  17.  *    distribution.
  18.  *
  19.  * 3. The end-user documentation included with the redistribution,
  20.  *    if any, must include the following acknowledgment:
  21.  *       "This product includes software developed by the
  22.  *        Apache Software Foundation (http://www.apache.org/)."
  23.  *    Alternately, this acknowledgment may appear in the software itself,
  24.  *    if and wherever such third-party acknowledgments normally appear.
  25.  *
  26.  * 4. The names "Apache" and "Apache Software Foundation" must
  27.  *    not be used to endorse or promote products derived from this
  28.  *    software without prior written permission. For written
  29.  *    permission, please contact apache@apache.org.
  30.  *
  31.  * 5. Products derived from this software may not be called "Apache",
  32.  *    nor may "Apache" appear in their name, without prior written
  33.  *    permission of the Apache Software Foundation.
  34.  *
  35.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  36.  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  37.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  38.  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  39.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  41.  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  42.  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  43.  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  44.  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  45.  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  46.  * SUCH DAMAGE.
  47.  * ====================================================================
  48.  *
  49.  * This software consists of voluntary contributions made by many
  50.  * individuals on behalf of the Apache Software Foundation.  For more
  51.  * information on the Apache Software Foundation, please see
  52.  * <http://www.apache.org/>.
  53.  */
  54.  
  55. /*
  56.  * This code draws heavily from the 4.4BSD <sys/queue.h> macros
  57.  * and Dean Gaudet's "splim/ring.h".
  58.  * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h>
  59.  * <http://www.arctic.org/~dean/splim/>
  60.  *
  61.  * We'd use Dean's code directly if we could guarantee the
  62.  * availability of inline functions.
  63.  */
  64. /**
  65.  * @file apr_ring.h
  66.  * @brief APR Rings
  67.  */
  68. #ifndef APR_RING_H
  69. #define APR_RING_H
  70.  
  71. /*
  72.  * for offsetof()
  73.  */
  74. #include "apr_general.h"
  75.  
  76. /**
  77.  * @defgroup APR_Rings Rings
  78.  * @ingroup APR
  79.  * @{
  80.  */
  81.  
  82. /**
  83.  * A ring is a kind of doubly-linked list that can be manipulated
  84.  * without knowing where its head is.
  85.  */
  86.  
  87. /**
  88.  * The Ring Element
  89.  *
  90.  * A ring element struct is linked to the other elements in the ring
  91.  * through its ring entry field, e.g.
  92.  * <pre>
  93.  *      struct my_element_t {
  94.  *          APR_RING_ENTRY(my_element_t) link;
  95.  *          int foo;
  96.  *          char *bar;
  97.  *      };
  98.  * </pre>
  99.  * An element struct may be put on more than one ring if it has
  100.  * more than one APR_RING_ENTRY field.
  101.  *
  102.  * @warning For strict C standards compliance you should put the APR_RING_ENTRY
  103.  * first in the element struct unless the head is always part of a larger
  104.  * object with enough earlier fields to accommodate the offsetof() used
  105.  * to compute the ring sentinel below. You can usually ignore this caveat.
  106.  */
  107. #define APR_RING_ENTRY(elem)                        \
  108.     struct {                                \
  109.     struct elem *next;                        \
  110.     struct elem *prev;                        \
  111.     }
  112.  
  113. /**
  114.  * The Ring Head
  115.  *
  116.  * Each ring is managed via its head, which is a struct declared like this:
  117.  * <pre>
  118.  *      APR_RING_HEAD(my_ring_t, my_element_t);
  119.  *      struct my_ring_t ring, *ringp;
  120.  * </pre>
  121.  *
  122.  * This struct looks just like the element link struct so that we can
  123.  * be sure that the typecasting games will work as expected.
  124.  *
  125.  * The first element in the ring is next after the head, and the last
  126.  * element is just before the head.
  127.  */
  128. #define APR_RING_HEAD(head, elem)                    \
  129.     struct head {                            \
  130.     struct elem *next;                        \
  131.     struct elem *prev;                        \
  132.     }
  133.  
  134. /**
  135.  * The Ring Sentinel
  136.  *
  137.  * This is the magic pointer value that occurs before the first and
  138.  * after the last elements in the ring, computed from the address of
  139.  * the ring's head.  The head itself isn't an element, but in order to
  140.  * get rid of all the special cases when dealing with the ends of the
  141.  * ring, we play typecasting games to make it look like one.
  142.  *
  143.  * @param hp   The head of the ring
  144.  * @param elem The name of the element struct
  145.  * @param link The name of the APR_RING_ENTRY in the element struct
  146.  */
  147. #define APR_RING_SENTINEL(hp, elem, link)                \
  148.     (struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))
  149.  
  150. /**
  151.  * The first element of the ring
  152.  * @param hp   The head of the ring
  153.  */
  154. #define APR_RING_FIRST(hp)    (hp)->next
  155. /**
  156.  * The last element of the ring
  157.  * @param hp   The head of the ring
  158.  */
  159. #define APR_RING_LAST(hp)    (hp)->prev
  160. /**
  161.  * The next element in the ring
  162.  * @param ep   The current element
  163.  * @param link The name of the APR_RING_ENTRY in the element struct
  164.  */
  165. #define APR_RING_NEXT(ep, link)    (ep)->link.next
  166. /**
  167.  * The previous element in the ring
  168.  * @param ep   The current element
  169.  * @param link The name of the APR_RING_ENTRY in the element struct
  170.  */
  171. #define APR_RING_PREV(ep, link)    (ep)->link.prev
  172.  
  173.  
  174. /**
  175.  * Initialize a ring
  176.  * @param hp   The head of the ring
  177.  * @param elem The name of the element struct
  178.  * @param link The name of the APR_RING_ENTRY in the element struct
  179.  */
  180. #define APR_RING_INIT(hp, elem, link) do {                \
  181.     APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link);    \
  182.     APR_RING_LAST((hp))  = APR_RING_SENTINEL((hp), elem, link);    \
  183.     } while (0)
  184.  
  185. /**
  186.  * Determine if a ring is empty
  187.  * @param hp   The head of the ring
  188.  * @param elem The name of the element struct
  189.  * @param link The name of the APR_RING_ENTRY in the element struct
  190.  * @return true or false
  191.  */
  192. #define APR_RING_EMPTY(hp, elem, link)                    \
  193.     (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
  194.  
  195. /**
  196.  * Initialize a singleton element
  197.  * @param ep   The element
  198.  * @param link The name of the APR_RING_ENTRY in the element struct
  199.  */
  200. #define APR_RING_ELEM_INIT(ep, link) do {                \
  201.     APR_RING_NEXT((ep), link) = (ep);                \
  202.     APR_RING_PREV((ep), link) = (ep);                \
  203.     } while (0)
  204.  
  205.  
  206. /**
  207.  * Splice the sequence ep1..epN into the ring before element lep
  208.  *   (..lep.. becomes ..ep1..epN..lep..)
  209.  * @warning This doesn't work for splicing before the first element or on
  210.  *   empty rings... see APR_RING_SPLICE_HEAD for one that does
  211.  * @param lep  Element in the ring to splice before
  212.  * @param ep1  First element in the sequence to splice in
  213.  * @param epN  Last element in the sequence to splice in
  214.  * @param link The name of the APR_RING_ENTRY in the element struct
  215.  */
  216. #define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do {        \
  217.     APR_RING_NEXT((epN), link) = (lep);                \
  218.     APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link);    \
  219.     APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1);    \
  220.     APR_RING_PREV((lep), link) = (epN);                \
  221.     } while (0)
  222.  
  223. /**
  224.  * Splice the sequence ep1..epN into the ring after element lep
  225.  *   (..lep.. becomes ..lep..ep1..epN..)
  226.  * @warning This doesn't work for splicing after the last element or on
  227.  *   empty rings... see APR_RING_SPLICE_TAIL for one that does
  228.  * @param lep  Element in the ring to splice after
  229.  * @param ep1  First element in the sequence to splice in
  230.  * @param epN  Last element in the sequence to splice in
  231.  * @param link The name of the APR_RING_ENTRY in the element struct
  232.  */
  233. #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do {            \
  234.     APR_RING_PREV((ep1), link) = (lep);                \
  235.     APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link);    \
  236.     APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN);    \
  237.     APR_RING_NEXT((lep), link) = (ep1);                \
  238.     } while (0)
  239.  
  240. /**
  241.  * Insert the element nep into the ring before element lep
  242.  *   (..lep.. becomes ..nep..lep..)
  243.  * @warning This doesn't work for inserting before the first element or on
  244.  *   empty rings... see APR_RING_INSERT_HEAD for one that does
  245.  * @param lep  Element in the ring to insert before
  246.  * @param nep  Element to insert
  247.  * @param link The name of the APR_RING_ENTRY in the element struct
  248.  */
  249. #define APR_RING_INSERT_BEFORE(lep, nep, link)                \
  250.     APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
  251.  
  252. /**
  253.  * Insert the element nep into the ring after element lep
  254.  *   (..lep.. becomes ..lep..nep..)
  255.  * @warning This doesn't work for inserting after the last element or on
  256.  *   empty rings... see APR_RING_INSERT_TAIL for one that does
  257.  * @param lep  Element in the ring to insert after
  258.  * @param nep  Element to insert
  259.  * @param link The name of the APR_RING_ENTRY in the element struct
  260.  */
  261. #define APR_RING_INSERT_AFTER(lep, nep, link)                \
  262.     APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
  263.  
  264.  
  265. /**
  266.  * Splice the sequence ep1..epN into the ring before the first element
  267.  *   (..hp.. becomes ..hp..ep1..epN..)
  268.  * @param hp   Head of the ring
  269.  * @param ep1  First element in the sequence to splice in
  270.  * @param epN  Last element in the sequence to splice in
  271.  * @param elem The name of the element struct
  272.  * @param link The name of the APR_RING_ENTRY in the element struct
  273.  */
  274. #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link)            \
  275.     APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link),    \
  276.                  (ep1), (epN), link)
  277.  
  278. /**
  279.  * Splice the sequence ep1..epN into the ring after the last element
  280.  *   (..hp.. becomes ..ep1..epN..hp..)
  281.  * @param hp   Head of the ring
  282.  * @param ep1  First element in the sequence to splice in
  283.  * @param epN  Last element in the sequence to splice in
  284.  * @param elem The name of the element struct
  285.  * @param link The name of the APR_RING_ENTRY in the element struct
  286.  */
  287. #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link)            \
  288.     APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link),    \
  289.                  (ep1), (epN), link)
  290.  
  291. /**
  292.  * Insert the element nep into the ring before the first element
  293.  *   (..hp.. becomes ..hp..nep..)
  294.  * @param hp   Head of the ring
  295.  * @param nep  Element to insert
  296.  * @param elem The name of the element struct
  297.  * @param link The name of the APR_RING_ENTRY in the element struct
  298.  */
  299. #define APR_RING_INSERT_HEAD(hp, nep, elem, link)            \
  300.     APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
  301.  
  302. /**
  303.  * Insert the element nep into the ring after the last element
  304.  *   (..hp.. becomes ..nep..hp..)
  305.  * @param hp   Head of the ring
  306.  * @param nep  Element to insert
  307.  * @param elem The name of the element struct
  308.  * @param link The name of the APR_RING_ENTRY in the element struct
  309.  */
  310. #define APR_RING_INSERT_TAIL(hp, nep, elem, link)            \
  311.     APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
  312.  
  313. /**
  314.  * Concatenate ring h2 onto the end of ring h1, leaving h2 empty.
  315.  * @param h1   Head of the ring to concatenate onto
  316.  * @param h2   Head of the ring to concatenate
  317.  * @param elem The name of the element struct
  318.  * @param link The name of the APR_RING_ENTRY in the element struct
  319.  */
  320. #define APR_RING_CONCAT(h1, h2, elem, link) do {            \
  321.     if (!APR_RING_EMPTY((h2), elem, link)) {            \
  322.         APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link),    \
  323.                   APR_RING_FIRST((h2)),            \
  324.                   APR_RING_LAST((h2)), link);        \
  325.         APR_RING_INIT((h2), elem, link);                \
  326.     }                                \
  327.     } while (0)
  328.  
  329. /**
  330.  * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.
  331.  * @param h1   Head of the ring to prepend onto
  332.  * @param h2   Head of the ring to prepend
  333.  * @param elem The name of the element struct
  334.  * @param link The name of the APR_RING_ENTRY in the element struct
  335.  */
  336. #define APR_RING_PREPEND(h1, h2, elem, link) do {            \
  337.     if (!APR_RING_EMPTY((h2), elem, link)) {            \
  338.         APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((h1), elem, link),    \
  339.                   APR_RING_FIRST((h2)),            \
  340.                   APR_RING_LAST((h2)), link);        \
  341.         APR_RING_INIT((h2), elem, link);                \
  342.     }                                \
  343.     } while (0)
  344.  
  345. /**
  346.  * Unsplice a sequence of elements from a ring
  347.  * @warning The unspliced sequence is left with dangling pointers at either end
  348.  * @param ep1  First element in the sequence to unsplice
  349.  * @param epN  Last element in the sequence to unsplice
  350.  * @param link The name of the APR_RING_ENTRY in the element struct
  351.  */
  352. #define APR_RING_UNSPLICE(ep1, epN, link) do {                \
  353.     APR_RING_NEXT(APR_RING_PREV((ep1), link), link) =        \
  354.              APR_RING_NEXT((epN), link);            \
  355.     APR_RING_PREV(APR_RING_NEXT((epN), link), link) =        \
  356.              APR_RING_PREV((ep1), link);            \
  357.     } while (0)
  358.  
  359. /**
  360.  * Remove a single element from a ring
  361.  * @warning The unspliced element is left with dangling pointers at either end
  362.  * @param ep   Element to remove
  363.  * @param link The name of the APR_RING_ENTRY in the element struct
  364.  */
  365. #define APR_RING_REMOVE(ep, link)                    \
  366.     APR_RING_UNSPLICE((ep), (ep), link)
  367.  
  368.  
  369. /**
  370.  * Iterate through a ring
  371.  * @param ep The current element
  372.  * @param hp The ring to iterate over
  373.  * @param elem The name of the element struct
  374.  * @param link The name of the APR_RING_ENTRY in the element struct
  375.  * @remark This is the same as either:
  376.  * <pre>
  377.  *    ep = APR_RING_FIRST(hp);
  378.  *     while (ep != APR_RING_SENTINEL(hp, elem, link)) {
  379.  *        ...
  380.  *         ep = APR_RING_NEXT(ep, link);
  381.  *     }
  382.  *   OR
  383.  *     for (ep = APR_RING_FIRST(hp);
  384.  *           ep != APR_RING_SENTINEL(hp, elem, link);
  385.  *           ep = APR_RING_NEXT(ep, link)) {
  386.  *        ...
  387.  *     }
  388.  * </pre>
  389.  * @warning Be aware that you cannot change the value of ep within
  390.  * the foreach loop, nor can you destroy the ring element it points to.
  391.  * Modifying the prev and next pointers of the element is dangerous
  392.  * but can be done if you're careful.  If you change ep's value or
  393.  * destroy the element it points to, then APR_RING_FOREACH
  394.  * will have no way to find out what element to use for its next
  395.  * iteration.  The reason for this can be seen by looking closely
  396.  * at the equivalent loops given in the tip above.  So, for example,
  397.  * if you are writing a loop that empties out a ring one element
  398.  * at a time, APR_RING_FOREACH just won't work for you.  Do it
  399.  * by hand, like so:
  400.  * <pre>
  401.  *      while (!APR_RING_EMPTY(hp, elem, link)) {
  402.  *          ep = APR_RING_FIRST(hp);
  403.  *          ...
  404.  *          APR_RING_REMOVE(ep, link);
  405.  *      }
  406.  * </pre>
  407.  */
  408. #define APR_RING_FOREACH(ep, hp, elem, link)                \
  409.     for ((ep)  = APR_RING_FIRST((hp));                    \
  410.      (ep) != APR_RING_SENTINEL((hp), elem, link);            \
  411.      (ep)  = APR_RING_NEXT((ep), link))
  412.  
  413. /**
  414.  * Iterate through a ring backwards
  415.  * @param ep The current element
  416.  * @param hp The ring to iterate over
  417.  * @param elem The name of the element struct
  418.  * @param link The name of the APR_RING_ENTRY in the element struct
  419.  * @see APR_RING_FOREACH
  420.  */
  421. #define APR_RING_FOREACH_REVERSE(ep, hp, elem, link)            \
  422.     for ((ep)  = APR_RING_LAST((hp));                    \
  423.      (ep) != APR_RING_SENTINEL((hp), elem, link);            \
  424.      (ep)  = APR_RING_PREV((ep), link))
  425.  
  426.  
  427. /* Debugging tools: */
  428.  
  429. #ifdef APR_RING_DEBUG
  430. #include <stdio.h>
  431. #define APR_RING_CHECK_ONE(msg, ptr)                    \
  432.     fprintf(stderr, "*** %s %p\n", msg, ptr)
  433. #define APR_RING_CHECK(hp, elem, link, msg)                \
  434.     APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
  435. #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do {            \
  436.     struct elem *start = (ep);                    \
  437.     struct elem *this = start;                    \
  438.     fprintf(stderr, "*** ring check start -- %s\n", msg);        \
  439.     do {                                \
  440.         fprintf(stderr, "\telem %p\n", this);            \
  441.         fprintf(stderr, "\telem->next %p\n",            \
  442.             APR_RING_NEXT(this, link));                \
  443.         fprintf(stderr, "\telem->prev %p\n",            \
  444.             APR_RING_PREV(this, link));                \
  445.         fprintf(stderr, "\telem->next->prev %p\n",            \
  446.             APR_RING_PREV(APR_RING_NEXT(this, link), link));    \
  447.         fprintf(stderr, "\telem->prev->next %p\n",            \
  448.             APR_RING_NEXT(APR_RING_PREV(this, link), link));    \
  449.         if (APR_RING_PREV(APR_RING_NEXT(this, link), link) != this) { \
  450.         fprintf(stderr, "\t*** this->next->prev != this\n");    \
  451.         break;                            \
  452.         }                                \
  453.         if (APR_RING_NEXT(APR_RING_PREV(this, link), link) != this) { \
  454.         fprintf(stderr, "\t*** this->prev->next != this\n");    \
  455.         break;                            \
  456.         }                                \
  457.         this = APR_RING_NEXT(this, link);                \
  458.     } while (this != start);                    \
  459.     fprintf(stderr, "*** ring check end\n");            \
  460.     } while (0)
  461. #else
  462. /**
  463.  * Print a single pointer value to STDERR
  464.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  465.  * @param msg Descriptive message
  466.  * @param ptr Pointer value to print
  467.  */
  468. #define APR_RING_CHECK_ONE(msg, ptr)
  469. /**
  470.  * Dump all ring pointers to STDERR, starting with the head and looping all
  471.  * the way around the ring back to the head.  Aborts if an inconsistency
  472.  * is found.
  473.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  474.  * @param hp   Head of the ring
  475.  * @param elem The name of the element struct
  476.  * @param link The name of the APR_RING_ENTRY in the element struct
  477.  * @param msg  Descriptive message
  478.  */
  479. #define APR_RING_CHECK(hp, elem, link, msg)
  480. /**
  481.  * Dump all ring pointers to STDERR, starting with the given element and
  482.  * looping all the way around the ring back to that element.  Aborts if
  483.  * an inconsistency is found.
  484.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  485.  * @param ep   The element
  486.  * @param elem The name of the element struct
  487.  * @param link The name of the APR_RING_ENTRY in the element struct
  488.  * @param msg  Descriptive message
  489.  */
  490. #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
  491. #endif
  492. /** @} */ 
  493. #endif /* !APR_RING_H */
  494.